#https://leetcode.cn/problems/subarrays-with-k-different-integers/solutions/598095/c-hua-dong-chuang-kou-li-jie-right-left-vzp76/

class Solution {
public:
    int f(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        map<int, int> cnt;
        for(int r = 0, l = 0; r < n; ++r) {
            cnt[nums[r]]++;
            while(cnt.size() > k) {
                cnt[nums[l]]--;
                if(!cnt[nums[l]]) cnt.erase(nums[l]);
                ++l;
            }
            ans += r - l + 1;
        }
        return ans;
    }

    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return f(nums, k) - f(nums, k - 1);
    }
};
